class Solution 
{
private:
    vector<int> curCombination;          // 当前组合
    vector<vector<int>> ret;                     // 算法解
    void deepSearch(int cur, int n, int k)
    {
        if (curCombination.size() + n - cur + 1 < k)
        {
            return;
        }
        if (curCombination.size() == k)
        {
            ret.push_back(curCombination);
            return;
        }

        curCombination.push_back(cur);
        deepSearch(cur + 1,n,k);
        curCombination.pop_back();
        deepSearch(cur + 1,n,k);
    }
public:
    vector<vector<int>> combine(int n, int k) 
    {
        deepSearch(1, n, k);
        return ret;
    }
};